package com.LeeCode;

/**
 * 第 N 个神奇数字
 */

public class Code878 {
    public static void main(String[] args) {
        int n = 1, a = 2, b = 3;
        System.out.println(new Code878().nthMagicalNumber(n, a, b));
    }

    public int nthMagicalNumber(int n, int a, int b) {
        final int MOD = 1_000_000_007;
        long lcm = a / gcd(a, b) * b;
        long left = Math.min(a, b) + n - 2; // 优化左区间
        long right = (long) Math.min(a, b) * n; // 开区间 (left, right)
        while (left + 1 < right) { // 开区间不为空
            long mid = (left + right) >>> 1;
            if (mid / a + mid / b - mid / lcm >= n) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return (int) (right % MOD);
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }

}
